"""
给出一个整数，从该整数中去掉 k个数字，要求剩下的数字形成的新整数尽可能小。 -- 不能打乱顺序
应该如何选取被去掉的数字？

其中整数的长度大于或等于 k，给出的整数的大小可以超越 Python语言中整型类型的最大值。


假设给出一个整数 1593212，删去3个数字，新整数最小的情况是 1212。
假设给出一个整数 30200，删去1个数字，新整数最小的情况是 200。
假设给出一个整数 10，删去2个数字（注意，这里要求删去的不是1个数字，而是2个），新整数的最小情况是 0

假设给出一个整数 3549，删去1个数字，新整数最小的情况是 349
"""


def remove_k_digist(num, k):
    """
    遍历 k 作为外循环，遍历数字 作为内循环

    1.每一次内层循环都需要从头开始遍历所有数字。
    例如，给出的整数是 11111111111114132，在第1轮循环中，需要遍历大部分数字，一直遍历到数字4，发现4>1，从而删除4。
    以目前的代码逻辑，下一轮循环时，还要从头开始遍历，再次重复遍历大部分数字，一直遍历到数字3，发现3>2，从而删除3。
    事实上，我们应该停留在上一次删除的位置继续进行比较，而不是再次从头开始遍历。

    2.字符串截取方法本身性能不高。
    字符串截取方法的底层实现，涉及新字符串的创建，以及逐个字符的复制。
    这个方法自身的时间复杂度是O（n）。
    因此，我们应该避免在每删除一个数字后就进行字符串的截取和拼接。
    """
    num = str(num)
    for i in range(0, k):
        has_cut = False
        # 从左向右遍历，找到比自己大的数，并删除
        for j in range(0, len(num) - 1):
            if num[j] > num[j + 1]:
                num = num[0:j] + num[j + 1:]
                has_cut = True
                break
        # 没有找到比自己大的数，删除最后一位
        if not has_cut:
            num = num[:-1]
    # 清除数字左侧的 0
    for j in range(0, len(num) - 1):
        if num[0] != 0:
            break
        num = num[1:len(num)]
    # 如果整数的所有数字都被删除了，直接返回 0
    if not len(num):
        return 0
    return int(num)


def remove_k_digist_v2(num, k):
    """遍历数字 作为外循环，遍历 k 作为内循环"""
    num = str(num)
    # 新整数的最终长度 = 原整数长度 - k
    new_length = len(num) - k
    # 创建一个栈，用于接收所有的数字
    stack = []

    for i in range(0, len(num)):
        # 遍历当前数字
        c = num[i]
        # 当栈顶数字大于遍历到的当前数字时，栈顶数字出栈，相当于删除数字
        while len(stack) and stack[len(stack)-1] > c and k > 0:
            stack.pop()
            k -= 1

        # 如果遇到数字 0 且栈为空则不入栈
        if "0" == c and not len(stack):
            new_length -= 1
            if new_length < 1:
                return 0
            continue

        # 遍历到的当前数字入栈
        stack.append(c)

    # 找到栈中的第一个非零数字的位置，以此构建新的整数字符串
    if new_length <= 0:
        return 0
    return "".join(stack)


print(remove_k_digist(3549, 1))
print(remove_k_digist_v2(3549, 1))
